\documentclass[11pt]{amsart}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{a4paper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{graphicx}
\usepackage[utf8x]{inputenc}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{listings}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}

\title{Syntax and Semantics of Babel-17}
\author{Steven Obua}
\date{\today}                                           % Activate to display a given date or no date

\newcommand{\metababel}[1] {\textsl{#1}}
\newcommand{\tabparbox}[1] {\parbox{12cm}{

\vspace{0.1cm}
#1
\vspace{0.1cm}
}}
\newcommand{\patterndescr}[1] {\parbox{9cm}{
\small
\vspace{0.1cm}
#1
\vspace{0.1cm}
}}
%\newcommand{\babelsrc}[1] {\texttt{#1}}
\newenvironment{babelcode}[0]{\begin{center}\tt}{\end{center}}

\lstdefinelanguage{babellanguage} 
{morekeywords={lazy, concurrent, match, case, exception, begin, end, random, await, true, false, infinity, val, def,module,private,public,protected,here,this,root, object,external,if,then,else,elseif,memoize,for,in,yield,
while,do,repeat,until,with,package},
sensitive=true, 
morecomment=[l]{//}, 
morecomment=[s]{/*}{*/}, 
morestring=[b]", 
} 

\lstset{language=babellanguage,mathescape=true,float, xleftmargin=1.5cm,columns=flexible}

\lstnewenvironment{babellisting} 
{\small} 
{} 

\newcommand{\babelsrc}[1] {\lstinline!#1!}


%\newenvironment{babellisting} [0]{\begin{center}\begin{babellistingfree}}{\end{babellistingfree}%\%end{center}}

%lstset{language=babellanguage,mathescape=true}\begin{lstlisting}}{\end{lstlisting}\end{center}}

 
\begin{document}



%\begin{abstract}
%Babel-17 is an evolving new programming language. In this paper I present Babel-17 v0.2. 
%\end{abstract}


\maketitle

\tableofcontents


\section{Introduction}
The first question that someone who creates a new programming language will  hear from others inevitably is: Why another programming language? Are there not already enough programming languages out there that you can pick from?

My answer to this question is: Because I always wanted to create a programming language in which I can express myself compactly and without jumping through too many hoopes, that is easy to understand and to learn, which allows me to apply software engineering principles like encapsulation, and which yields efficient enough programs. And now I feel that I have gathered enough knowledge and experience to start walking towards this goal. 

Babel-17 is not a radically new or revolutionary programming language. It picks those raisins I like out of languages like Standard ML, Alice ML, Java, Scala, Erlang, Haskell, Lisp, Clojure and Mathematica, and tries to evolve them into a beautiful new design. Of course, what some regard as beautiful, others might find unremarkable, or even ugly.

Babel-17 is a functional language. It is not a pure functional language because it contains sources of non-determinism like the ability to pick one of two values randomly. If you take these sources of non-determinism out of the language, it becomes pure. Therefore I call Babel-17 a \emph{clean} functional language.

In Babel-17, every value has a type. These types are not checked statically, but only dynamically. 

Babel-17 is also object-oriented in that many aspects of Babel-17 can be explained in terms of sending messages to objects. 

The default evaluation order of Babel-17 is strict. But optional laziness is built into the heart of Babel-17, also, and so is concurrency. 

Babel-17 has pattern matching and exception handling. Both are carefully integrated with each other and with the laziness and concurrency capabilities of Babel-17.

Furthermore, Babel-17 establishes the paradigm of \emph{functional structured programming}  via the notion of linear scope.

In this paper  I specify Babel-17 v0.2 in a mostly informal style: formal notation is sometimes used when it supports clarity.

\section{Lexical Matters}
Babel-17 source code is always written UTF-8 encoded. If it ain't UTF-8, it ain't Babel-17. 

Constructors are alphanumeric strings which can also contain underscores, and which must start with a capital letter. 
Identifiers are alphanumeric strings which can also contain underscores, and which must start with a non-capital letter.
The distinction between two constructors or two identifiers is not sensitive to capitalization.

These are the keywords of Babel-17:
\begin{center}
\tt
\begin{tabular}{cccccccc}
begin & end & object & with & if & then & else & elseif \\
while &  for & do & module & package & yield & match & case \\
as & val & def & in & exception & lazy & concurrent & memoize \\
to & downto & true & false & this & random & infinity & await \\
private & public & protected & here & root & external &  &
\end{tabular}
\end{center}
Note that keywords are written always in lower case. For example, {\tt bEGIN} is not a legal keyword, but it also isn't an identifier (because of case insensitivity). Also note that {\tt Begin} and {\tt BEGIN} denote the same legal constructor. When we talk about identifiers in the rest of the paper, we always mean identifiers which are not keywords.

You can write down decimal, hexadecimal, binary and octal numbers in Babel-17. The following notations all denote the same number:
\begin{center}
\tt
\begin{tabular}{cccc}
15 & 0xF & 0b1111 &  0o17
\end{tabular}
\end{center}
Babel-17 also knows the number \babelsrc{infinity}.

Strings start and end with a quotation mark. Between the quotation mark, any valid UTF-8 string is allowed that does not contain newline, backslash or quotation mark characters, for example:
\begin{center}
\begin{tabular}{cccc}
\verb+"hello world"+ & \verb+"$1, 2%"+ & \verb+"1 <= 4! <= 5^2"+
\end{tabular}
\end{center}
Newline, backslash and quotation mark characters can be written down in escaped form. Actually, any unicode character can be written down in its escaped form via the hexadecimal value of its codepoint: 
\begin{center}
\begin{tabular}{r|l}
String consisting only of a quotation mark & \verb+"\""+\\\hline
String consisting only of a backslash & \verb+"\\"+ \\\hline
String consisting only of a line feed & \verb+"\n"+ \\\hline
String consisting only of a carriage return & \verb+"\r"+ \\\hline
String consisting only of line feed via 16-bit escaping & \verb+"\u000A"+ \\\hline
String consisting only of line feed via 32-bit escaping & \verb+"\U0000000A"+
\end{tabular}
\end{center}

Comments in Babel-17 obey the same syntax as in C: There are multiline comments written between matching pairs of \verb+/*+ and \verb+*/+, and there are comments that occupy the rest of the line which start with a \verb+//+.

Finally, here are all ASCII special symbols that can occur in a Babel-17 program:
\newcommand{\mapcurlyleft}{\{|}
\begin{center}
\tt
\begin{tabular}{ccccccccccccc}
\verb+==+ & \verb+!=+ & \verb+<>+ & \verb+<+ & \verb+<=+ & \verb+>+& \verb+>=+  &
\verb-+- & \verb+-+ & \verb+*+ & \verb+/+ & \verb+%+ & \verb+^+  \\
\verb-|- & \verb+&+ & \verb+!+ & \verb-++- & \verb+--+& \verb+**+  &
\verb-;- & \verb+,+ & \verb+::+ & \verb+->+ & \verb+=>+& \verb+?+  & \verb+...+  \\
\verb-(- & \verb+)+ & \verb+[+ & \verb+]+ & \verb+{+& \verb+}+  & \verb+.+ &  \verb+=+  &
\verb+@+ & & & 
\end{tabular}
\end{center}
Table~\ref{table:furthersymbols} lists all other Unicode symbols that have a meaning in Babel-17.
\begin{table}
\caption{Further Unicode Symbols}
\begin{tabular}{c|c|c}
\textbf{Unicode Hex Code} & \textbf{Display} & \textbf{ASCII Equivalent}\\\hline
%\parbox{0cm}{\vspace{0.7cm}}2983 & \texttt{\{\hspace{-0.089cm}∣} & \verb+{|+\\
%2984 & \texttt{∣\hspace{-0.089cm}\}} & \verb+|}+\\
2261 & ≡ & \verb+==+\\
2262 & ≢ & \verb+!=+\\
2264 & ≤ & \verb+<=+\\
2265 &  ≥ & \verb+>=+\\
221E & ∞ & \babelsrc{infinity}\\ 
2227 & ∧ & \verb+&+\\
2228 & ∨ & \verb+|+\\
00AC & ¬ & \verb+!+\\
2237 & :: & \verb+::+\\
2192 & → & \verb+->+\\
21D2 & ⇒ & \verb+=>+\\
2026 & … & \verb+...+\\
\end{tabular}
\label{table:furthersymbols}
\end{table}


\section{Overview of Built-in Types}
Each value in Babel-17 has a unique type. All built-in types are depicted in Table~\ref{table:builtintypes}.
\begin{table}
\caption{Built-in Types of Babel-17}
\begin{tabular}{c|c}
\textbf{Type} & \textbf{Description}\\\hline
\metababel {Integer} & the type of arbitrary size integer numbers\\
\metababel{Infinity} & the type consisting of the values \babelsrc{infinity} and \babelsrc{-infinity}\\
\metababel{Boolean} & the type consisting of the values \babelsrc{true} and \babelsrc{false}\\
\metababel{String} & the type of valid Unicode strings\\
\metababel{List} & the type of lists / tuples\\
\metababel{Set} & the type of sets \\
\metababel{Map}& the type of maps \\
\metababel{CExpr} & the type of constructed expressions\\
\metababel{Object} & the type of user-defined objects\\
\metababel{Function} & the type of  functions\\
\metababel{PersistentException} & the type of persistent exceptions\\
\metababel{DynamicException} & the type of dynamic exceptions\\
\metababel{Module} & the type of modules\\
\metababel{ModuleKey} & the type of module keys\\
\end{tabular}
\label{table:builtintypes}
\end{table}

\section{Objects and Functions}
All values in Babel-17 are objects. This means that you can send messages to them. Many values in Babel-17 are functions. This means that you can apply them to an argument, yielding another value. Note that for a value to be an object, it does not need to have type \metababel{Object}, and for a value to be a function,  it does not need to have type \metababel{Function}. 

The result of sending message $m$ to object $v$  is written as
\begin{babellisting}
$v$.$m$
\end{babellisting}
Here $m$ is an identifier. 
The result of applying function $f$ to value $x$ is written as 
\begin{babellisting}
$f$ $x$
\end{babellisting}
Note that $f$ $x$ is equivalent to 
\begin{babellisting}
($f$.apply) $x$
\end{babellisting}
Therefore any object that responds to the \babelsrc{apply} message can act as a function.
In the above we could also leave out the brackets because sending messages binds stronger than function application. 

Repeated function application associates to the left, therefore 
\begin{babellisting}
$f$ $x$ $y$ 
\end{babellisting} 
is equivalent to \babelsrc{($f$\ $x$)\ $y$}.

\section{Exceptions}
Exception handling in Babel-17 mimicks exception handling mechanisms like those which can be found in Java or Standard ML or Erlang, while adhering at the same time to the functional paradigm .

There are two types of exceptions: \metababel{PersistentException} and  \metababel{DynamicException}.
The difference is that a \metababel{PersistentException}  can be treated as part of any data structure, and is passed around just like any other value, while a \metababel{DynamicException} can never be part of a data structure and has special evaluation semantics. 

Exceptions in Babel-17 are not that special at all but mostly just another type of value.  Let us write \metababel{PersistentException $v$} for a \metababel{PersistentException} with parameter $v$,
and  \metababel{DynamicException $v$} for a \metababel{DynamicException} with parameter $v$. 
We also write \metababel{Exception $v$} for an exception with parameter $v$. The parameter $v$ is a non-exceptional value; this means that $v$ can be any Babel-17 value except one of type \metababel{DynamicException}. Note that $v$ can be non-exceptional and of type \metababel{PersistentException} at the same time.

Then the following deterministic rules govern how exceptions behave with respect to sending of messages, function application, laziness and concurrency:
\begin{babelcode}
\begin{tabular}{rcll}
(\metababel{Exception $v$}).$m$ & $\leadsto$ & \metababel{DynamicException $v$}&\\
(\textsl{Exception} $v$) $x$ & $\leadsto$ & \metababel{DynamicException $v$}&\\
$f$ (\metababel{DynamicException $v$}) & $\leadsto$ & \metababel{DynamicException $v$}& {\rm where $f$ is non-exceptional}\\
exception $v$ & $\leadsto$ & \metababel{DynamicException $v$}&\\
lazy (\metababel{Exception $v$}) & $\leadsto$ & \metababel{PersistentException $v$}&\\
concurrent (\metababel{Exception $v$}) & $\leadsto$ & \metababel{PersistentException $v$}&\\
\end{tabular}\\
\end{babelcode}
Exceptions in Babel-17 are created with the expression \babelsrc{exception $\ v$}. Creating exceptions in Babel-17 corresponds to \emph{raising} or \emph{throwing} exceptions in other languages. There is no special construct for catching exceptions in Babel-17. Instead, catching an exception can be done via the \babelsrc{match} expression which will be described later. 

In a later section, we will describe the  \babelsrc{lazy} and \babelsrc{concurrent} expressions of Babel-17. They are the reason why exceptions are divided into dynamic and persistent ones. 

\section{Laziness and Concurrency}
The default evaluation mechanism of Babel-17 is strict. This basically means that the arguments of a function are evaluated before the function is applied to them. Babel-17 has two constructs to change this default behaviour. 

The expression
\begin{babellisting}
lazy $e$
\end{babellisting}
is not evaluated until it is actually needed. When it is needed, it evaluates to whatever $e$ evaluates to, with the exception of dynamic exceptions, which are converted to persistent ones. It is guaranteed that $e$ is only evaluated once. 

The expression
\begin{babellisting}
concurrent $e$
\end{babellisting}
also evaluates to whatever $e$ evaluates to, again with the exception of dynamic exceptions which are converted to persistent ones. This evaluation will happen concurrently.  
It is guaranteed that $e$ is only evaluated once.

One could think that apart from obvious different performance characteristics, the expressions \babelsrc{lazy $\ e$} and \babelsrc{concurrent $\ e$} are equivalent. This is not so.
If $e$ is a non-terminating expression then, even if  the value of  \babelsrc{concurrent  $\ e$} is never needed during program execution, it might still lead to a non-terminating program execution. In other words, the behaviour of \babelsrc{concurrent $\ e$}  is unspecified for non-terminating $e$.

\section{Lists and Vectors}
For $n \ge 0$, the expression
\begin{babellisting}
[$e_1$, $\ldots$, $e_n$]
\end{babellisting}
denotes a \emph{list} of $n$ elements. 

The expression
\begin{babellisting}
($e_1$, $\ldots$, $e_n$)
\end{babellisting}
denotes a  \emph{vector} of $n$ elements, at least for $n \neq 1$. 
For $n=1$, there is a problem with notation, though, because \babelsrc{($e$)}  is equivalent to $e$. Therefore there is the special notation \babelsrc{($e$,)} for vectors which consist of only one element.

The only difference between lists and vectors is that they have different performance characteristics for the possible operations on them. Lists behave like simply linked lists, and vectors behave like arrays. Note that all data structures in Babel-17 are immutable. Apart from performance characteristics, anywhere you can use a list, you can use a vector, and vice versa. 

Another way of writing down lists is via the right-associative \babelsrc{::} constructor:
\begin{babellisting}
$h$::$t$
\end{babellisting}
Here $h$ denotes the \emph{head} of the list and $t$ its \emph{tail}. Actually, note that the expression \babelsrc{[$e_1$, $\ldots$, $e_n$]} is just syntactic sugar for the expression
\begin{babellisting}
$e_1$::$e_2$::$\ldots$::$e_n$::[]
\end{babellisting}
Dynamic exceptions cannot be part of a list but are propagated:
\begin{babelcode}
\begin{tabular}{rcll}
(\metababel{DynamicException $v$})::$t$ & $\leadsto$ & \metababel{DynamicException $v$}&\\
$h$::(\metababel{DynamicException $v$}) & $\leadsto$ & \metababel{DynamicException $v$}& {\rm where $h$ is non-exceptional}\\
\end{tabular}\\
\end{babelcode}

\section{CExprs}
A \metababel{CExpr} is a constructor $c$ together with a parameter $p$, written $c$ $p$. It is allowed to leave out the parameter $p$, which then defaults to \babelsrc{()}. For example,  \babelsrc{HELLO} is equivalent to \babelsrc{HELLO ()}. A constructor $c$ cannot have a dynamic exception as its parameter, therefore we have:
\begin{babelcode}
\begin{tabular}{rcll}
$c$ (\metababel{DynamicException $v$}) & $\leadsto$ & \metababel{DynamicException $v$}&\\
\end{tabular}\\
\end{babelcode}

\section{Pattern Matching}
Maybe the most powerful tool in Babel-17 is pattern matching. You use it in several places, most prominently in the \babelsrc{match} expression which has the following syntax:
\begin{babellisting}
match $e$ 
  case $p_1$ => $b_1$
  $\vdots$
  case $p_n$ => $b_n$
end  
\end{babellisting}
Given a value $e$, Babel-17 tries to match it to the patterns $p_1$, $p_2$, $\ldots$ and so on sequentially in that order. If $p_i$ is the first pattern to match, then the result of \babelsrc{match} 
is given by the block expression $b_i$. If none of the pattern matches then there are two possible outcomes:
\begin{enumerate}
\item If $e$ is a dynamic exception, then the value of the match is just $e$.
\item Otherwise the result is a dynamic exception with parameter \babelsrc{NoMatch $\ e$}.
\end{enumerate}
A few of the pattern constructs are capable of raising dynamic exceptions because they incorporate arbitrary value expressions. When during a pattern match such an exception occurs, then the entire match is aborted and the dynamic exception is returned as the result of the \babelsrc{match}-expression. Furthermore note that persistent exceptions in $e$ or any of the patterns also lead to a dynamic exception if the value of the persistent exception is forced for pattern matching.

So what does a pattern look like? Table~\ref{table:patterns} lists all ways of building a pattern.
\begin{table}
\caption{Pattern Constructs in Babel-17}
\begin{tabular}{c|l}
\textbf{Syntax} & \textbf{General Description}\\\hline
\babelsrc{_} & \patterndescr{the underscore symbol matches anything but a dynamic exception}\\\hline
\babelsrc{$x$} & \patterndescr{an identifier $x$ matches anything but a dynamic exception and binds the matched expression to $x$}\\\hline
\babelsrc{($x\ $ as $\ p$)} & \patterndescr{matches $p$, and binds the successfully matched value to $x$; the match fails if $p$ does not match or if the matched value is a dynamic exception}\\\hline
\babelsrc{$z$} & \patterndescr{a number $z$, like \babelsrc{0} or \babelsrc{42} or \babelsrc{-10} or 
\babelsrc{infinity} or \babelsrc{-infinity} , matches just that number $z$}\\\hline
\babelsrc{$c\ $ $p$} & \patterndescr{matches a \metababel{CExpr} with constructor $c$ if the parameter of the \metababel{CExpr} matches $p$}\\\hline
\babelsrc{$s$} & \patterndescr{a string $s$, like \babelsrc{"hello"}, matches just that string $s$}\\\hline
\babelsrc{[$p_1$, $\ \ldots\ $, $\ p_n$]} &  \patterndescr{matches a list consisting of $n \ge 0$ elements, such that element $e_i$ of the list is matched by pattern $p_i$}\\\hline
\babelsrc{($p_1$, $\ \ldots\ $, $\ p_n$)} &  \patterndescr{matches a list consisting of $n=0$ or $n \ge 2$ elements, such that element $e_i$ of the list is matched by pattern $p_i$}\\\hline
\babelsrc{($p$)} & \patterndescr{same as $p$} \\\hline
\babelsrc{[$p_1$, $\ \ldots\ $, $\ p_n$, $\ \delta$]} &  \patterndescr{matches a list/vector consisting of at least $n \ge 0$ elements, such that the first $n$ elements $e_i$ of the list/vector are matched by the patterns $p_i$}\\\hline
\babelsrc{($p_1$, $\ \ldots\ $, $\ p_n$, $\ \delta$)} &  \patterndescr{matches a vector/list consisting of at least $n \ge 0$ elements, such that the first $n$ elements $e_i$ of the vector/list are matched by the patterns $p_i$}\\\hline
\babelsrc{($p$, )} &  \patterndescr{matches a vector/list consisting of a single element that matches the pattern $p$.} \\\hline
\babelsrc{($h$::$t$)} & \patterndescr{matches a non-empty list/vector such that $h$ matches the head of the list/vector and $t$ its tail}\\\hline
\babelsrc{($p\ $ if $\ e$)} & \patterndescr{matches $p$, but only if $e$ evaluates to \babelsrc{true}; identifiers bound in $p$ can be used in $e$}\\\hline
\babelsrc{(val $\ e$)} & \patterndescr{matches any value which is equivalent to $e$}\\\hline
\babelsrc{($f\ $ ? $\ p$)} & \patterndescr{here $f$ is a function; $f$ is applied to the value to be matched; the match succeeds if the result of the application is \babelsrc{(Some $\ r$)} and $p$ matches $r$, or if the result is \babelsrc{true} and $p$ matches $()$.}\\\hline
\babelsrc{($d\ $ ? $\ p$)} & \patterndescr{here $d$ is a not a function and non-exceptional;   calculate the result of \babelsrc{($v$.deconstruct $\ d$)} where $v$ denotes the value to be matched; the match succeeds if the result  is \babelsrc{(Some $\ r$)} and $p$ matches $r$, or if the result is \babelsrc{true} and $p$ matches $()$ }\\\hline
\babelsrc{($e\ $ ?)} & \patterndescr{same as \babelsrc{($e\ $ ? _)}}\\\hline
\babelsrc{\{$p_1$,$\ \ldots\ $,$\ p_n$\}} & \patterndescr{matches any set such that every element of the set matches some $p_i$, and such that every $p_i$ is matched by some element of the set}\\\hline
\babelsrc{\{$p_1$,$\ \ldots\ $,$\ p_n\ $, $\ \delta$\}} & \patterndescr{matches any set such that every $p_i$ is matched by some element of the set}\\\hline
\babelsrc{\{$k_1\ $ -> $\ v_1$,$\ \ldots\ $,$\ k_n\ $ -> $\ v_n$\}} & \patterndescr{matches any map that can be constructed from the $n$ key-value patterns}\\\hline
\babelsrc{\{$k_1\ $ -> $\ v_1$,$\ \ldots\ $,$\ k_n\ $ -> $\ v_n$, $\ \delta$\}} & \patterndescr{matches any map that contains the $n$ key-value patterns}\\\hline
\babelsrc{\{->\}} & \patterndescr{matches the empty map }

\end{tabular}
\label{table:patterns}
\end{table}


In this table of pattern constructions we use the $\delta$-pattern $\delta$. This pattern stands for "the rest of the collection under consideration" and can be constructed by the following rules:
\begin{enumerate}
\item The ellipsis \babelsrc{...} is a $\delta$-pattern that matches any collection.
\item If $\delta$ is a $\delta$-pattern, and $x$ an identifier, then \babelsrc{($x\ $ as $\ \delta$)} is a $\delta$-pattern.
\item If $\delta$ is a $\delta$-pattern, and $e$ an expression, then \babelsrc{($\delta\ $ if $\ e$)} is a $\delta$-pattern.
\item If $\delta$ is a $\delta$-pattern, and $e$ an expression, then \babelsrc{($e\ $ ? $\ \delta$)} is a $\delta$-pattern.\end{enumerate}

Note that pattern matching does not distinguish between vectors and lists. A pattern that looks like a vector can match a list, and vice versa.

\section{Non-Determinism in Babel-17}

The possibility of matching sets and maps introduces non-determinism into Babel-17. For example, the expression
\begin{babellisting}
match {1, 2}
  case {x, ...} => x
end
\end{babellisting}
can return both 1 and 2. 

Another source of non-determinism is \emph{probabilistic} non-determism. The expression
\begin{babellisting}
random $n$
\end{babellisting}
returns for an integer $n > 0$ a number between $0$ and $n-1$ such that each number between $0$ and $n-1$ has equal chance of being returned. If $n$ is a dynamic exception, then this exception is propagated, if $n$ is a non-exceptional value that is not an integer $> 0$ then the result is an exception with parameter \babelsrc{InvalidArgument $\ n$}.

The third source of non-determinism is \emph{concurrent} non-determism. The expression
\begin{babellisting}
await $l$
\end{babellisting}
takes a finite list $l$ of possibly concurrently evaluated expressions and waits until  at least one of the element expressions has finished computing. It returns a list of the element expressions that have been computed so far.
Again, in case $l$ is non-exceptional and not a finite  list, the result is an exception with parameter
\babelsrc{InvalidArgument $\ l$}. If $l$ is a dynamic exception, then it is propagated such that the result is $l$. 

\section{Block Expressions}
So far we have only looked at expressions. We briefly mentioned the term \emph{block expressions} in the description of the \babelsrc{match} function, though.  We will now introduce and explain block expressions.

Block expressions can be used in several places as defined by the Babel-17 grammar. For example, they can be used in a \babelsrc{match} expression to define the value that corresponds to a certain case. But block expressions can really be used just everywhere where a normal expression is allowed: 
\begin{babellisting}
begin
  $b$
end
\end{babellisting}
is a normal expression where $b$ is a block expression. A block expression has the form
\begin{babellisting}
$s_1$
$\vdots$
$s_n$
$e$
\end{babellisting}
where the $s_i$ are statements and $e$ is the return expression of the block (a return expression is just a normal expression). In a block expression newlines can be used to separate the statements and the return expression from each other. The other means of separation are semicolons. Later on we will see how block expressions can be used to imitate imperative programming; on those occasions there will be no return expression $e$ but only statements.

Statements are Babel-17's primary tool for introducing identifiers. There are several kinds of statements. Two of them will be introduced in this section.

First, there is the \babelsrc{val}-statement which has the following syntax:
\begin{babellisting}
val $p$ = $e$
\end{babellisting}
Here $p$ is a pattern and $e$ is an expression. Its meaning is that $e$ gets evaluated and then is matched to $p$. If the match is successful then all identifiers bound by the match can be used in later statements and in the return expression of the block expression. Otherwise, some kind of dynamic exception must have happened which then becomes the value of the entire block expression. 

Second, there is the \babelsrc{def}-statement which obeys the following syntax for defining the identifier $id$:
\begin{babellisting}
def $id$ $arg$ = $e$
\end{babellisting}
The $arg$ part is optional. If $arg$ is present, then it must be a pattern. Let us call those definitions where $arg$ is present a \emph{function definition}, and those definitions where $arg$ is not present a \emph{simple definition}.  

Per block expression and identifier $id$ there can be either a single simple definition, or there can be several function definitions. If there are multiple function definitions for the same identifier, then they must appear sequentially in the block expression, without any other statements interrupting the sequence.

The defining expressions in  \babelsrc{def}-statements can recursively refer to the other identifiers defined by  \babelsrc{def}-statements in the same block expression. This is the main difference between definitions via \babelsrc{def} and definitions via \babelsrc{val}. Only those \babelsrc{val}-identifiers are in scope that have been defined \emph{previously}. Table~\ref{table:legaldef} exemplifies this rule.
\begin{table}
\caption{Legal and illegal definitions}
\begin{tabular}{c@{\hspace{1cm}}c@{\hspace{1cm}}c@{\hspace{1cm}}c}
\begin{babellisting}
val x = y       
val y = 0
\end{babellisting} &
\begin{babellisting}
def x = y       
val y = 0
\end{babellisting} &
\begin{babellisting}
val x = y       
def y = 0
\end{babellisting} &
\begin{babellisting}
def x = y       
def y = 0
\end{babellisting} \\[0.5cm]
\emph{illegal} &
\emph{illegal} &
\emph{legal} &
\emph{legal} 
\end{tabular}
\label{table:legaldef}
\end{table}

Let us assume that  a block expression contains multiple function definitions for the same identifier \babelsrc{f}:
\begin{babellisting}
def f $p_1$ = $e_1$ 
   $\vdots$
def f $p_n$ = $e_n$ 
\end{babellisting}
Then this is equivalent to 
\begin{babellisting}
def f x = 
  match x
    case $p_1$ => $e_1$
      $\vdots$
    case $p_n$ => $e_n$ 
  end
\end{babellisting}
where \babelsrc{x} is fresh for the $p_i$ and $e_i$.

While only one simple definition per block and identifier is allowed, it is ok to have multiple \babelsrc{val}-statements for the same identifier in one block expression, for example like that:
\begin{babellisting}
val x = 1
val x = (x, x)
x
\end{babellisting}
The above block expression evaluates to \babelsrc{(1,1)}; later \babelsrc{val}-definitions overshadow earlier ones.
But note that neither
\begin{babellisting}
val x = 1
def x = 1
\end{babellisting}
nor
\begin{babellisting}
def x = 1
val x = 1
\end{babellisting}
are legal.

Another difference between \babelsrc{val} and \babelsrc{def} is observed by the effects of non-determinism:
\begin{babellisting}
val x = random 2
(x, x)
\end{babellisting}
will evaluate either to \babelsrc{(0, 0)} or to \babelsrc{(1, 1)}. But 
\begin{babellisting}
def x = random 2
(x, x)
\end{babellisting}
can additionally also evaluate to \babelsrc{(0, 1)} or to \babelsrc{(1, 0)}. The reason for this is that above code snippet is syntactic sugar for:
\begin{babellisting}
def x () = random 2
(x(), x())
\end{babellisting}

\emph{ToDo: need to explain more about order of vals and defs, especially that vals cannot reference later vals, even not indirectly via defs. This will also clean up the parts about module and object initialization.}

\section{Anonymous Functions}
So far we have seen how to define named functions in Babel-17. Sometimes we do not need a name for a certain function, for example when the code that implements this function is actually just as easy to understand as any name for the function. We already have the tools for writing such nameless, or anonymous, functions:
\begin{babellisting}
begin
  def sqr x = x * x 
  sqr
end
\end{babellisting}
is an expression denoting the function that squares its argument. There is a shorter and equivalent way of writing down the above:
\begin{babellisting}
x => x * x
\end{babellisting}
In general, the syntax is
\begin{babellisting}
$p$ => $e$
\end{babellisting}
where $p$ is a pattern and $e$ an expression. The above is equivalent to
\begin{babellisting}
begin
  def f $p$ = $e$ 
  f
end
\end{babellisting}
where \babelsrc{f} is fresh for $p$ and $e$.


There is also a syntax for anonymous functions which allows for several cases:
\begin{babellisting}
(case $p_1$ => $b_1$
    $\vdots$
 case $p_n$ => $b_n$)
\end{babellisting}
is equivalent to 
\begin{babellisting}
begin
  def f $p_1$ = begin $b_1$ end
    $\vdots$
  def f $p_n$ = begin $b_n$ end
  f
end
\end{babellisting}
where $\babelsrc{f}$ is fresh for the $p_i$ and $b_i$.

\section{Modules}
Modules are Babel-17's way to structure programs and to define access boundaries. A module has the following syntax:
\begin{babellisting}
module $m$ 
  $s_1$
  $\vdots$
  $s_n$
end
\end{babellisting}
The $s_i$ are  \babelsrc{val} or \babelsrc{def} statements, or they are themselves again \emph{nested} module definitions / declarations. 
Nested module definitions have the following syntax:
\begin{babellisting}
$\metababel{attr}$ module $m$ 
  $s_1$
  $\vdots$
  $s_n$
end
\end{babellisting}
Nested module declarations look as follows:
\begin{babellisting}
$\metababel{attr}$ external module $m$
\end{babellisting}
The $m$ always is a \emph{module path}. A module path consists of a non-empty sequence of identifiers which are separated by periods. For example, \texttt{lang} is a module path, and so is  \texttt{lang.math.taylor}.  For nested module definitions/declarations, $m$ cannot contain any periods.
Nested modules have an attribute \metababel{attr} which can be either \babelsrc{public} or \babelsrc{protected} or \babelsrc{private}. If there is no explicit attribute given, then the default attribute is \babelsrc{private}. These attributes are also used for those statements $s_i$ which are \babelsrc{def} statements, again with the default being \babelsrc{private} .

Before explaining what these attributes mean, let us first look at \emph{inner} and \emph{outer submodules}. Examples of both are given in Figure~\ref{fig:innermodule}.
In both example cases, the absolute module path of the submodule is \texttt{root.main.sub}. The absolute module path of the main module is \texttt{root.main}. 
\begin{figure}
\caption{Inner Submodule vs. Outer Submodule}
\begin{center}

\vspace{0.2cm}
\begin{tabular}{c|c}
\emph{Inner Submodule} & \emph{Outer Submodule} \\\hline
\begin{babellisting}
module main
  $s_1$
  $\vdots$
  $s_{i-1}$
  $\metababel{attr}$ module sub 
    $\vdots$ 
  end
  $s_{i+1}$
  $\vdots$
  $s_n$
end
\end{babellisting} &
\begin{babellisting}
module main
  $s_1$
  $\vdots$
  $s_{i-1}$
  $\metababel{attr}$ external module sub   
  $s_{i+1}$
  $\vdots$
  $s_n$
end
module main.sub
  $\vdots$ 
end
\end{babellisting} 
\end{tabular}
\end{center}
\label{fig:innermodule}
\end{figure}
This means that there is a \emph{root module} which is the only module that has no \emph{supermodule}. For every other module, the supermodule must exist. In other words, we can view the set of modules as a tree, such that the child of a node is a submodule of the module represented by this node, and such that for each node there is a unique module definition. If a node is an inner submodule, then all its children must be inner submodules, too.

The semantic difference between an inner and an outer submodule is that the inner submodule imports the namespace of its parent; more specifically, the inner submodule imports from the parent module all \babelsrc{def} and \babelsrc{module} definitions, but only those \babelsrc{val} definitions that come before the inner submodule definition. 

The reserved keyword \babelsrc{here} denotes the current module.
The reserved keyword \babelsrc{root} denotes the root module.

A module is an object, just like all other values in Babel-17. The messages it can successfully receive depend on its \babelsrc{def} and \babelsrc{module} statements, their attributes, and the module of the sender.
For two modules $P$ and $Q$ we write $P = Q$ iff $P$ and $Q$ denote the same module (i.e. they have the same absolute module path), and $P \lhd Q$ iff not $P = Q$ and $Q$ is a direct or indirect submodule of the module $P$.
We write $P  \lhd_i Q$ iff $P \lhd Q$ and the child of $P$ on the path to $Q$ is an inner submodule. We write
 $P  \lhd_o Q$ iff $P \lhd Q$ and not $P \lhd_i Q$.
In Table~\ref{table:moduleaccess} \babelsrc{here} denotes the module to which the message is sent, and \emph{sender} denotes the module from where the message is sent. The table shows if a message send is successful ($+$ means yes, $-$ means no), depending on the relation between \babelsrc{here} and \emph{sender}, and depending on the attribute of the defining statement.
\begin{table}
\caption{Rules of Module Access}
\begin{tabular}{c||c|c|c|c}
  &  \babelsrc{here} $=$ \emph{sender} & \babelsrc{here} $\lhd_i$ \emph{sender} & \babelsrc{here} $\lhd_o$ \emph{sender} & otherwise \\\hline\hline
 \babelsrc{private} & + & + & - & - \\\hline
 \babelsrc{protected} & + & + & + & - \\\hline
 \babelsrc{public} & + & + & + & + 
\end{tabular}
\label{table:moduleaccess}
\end{table}

Before a module can be used as an object, it must be initialized. The result of a complete initialization is that all \babelsrc{val} statements of the module have been executed, and that all inner submodules of the module have been initialized, too, all in the order of their appearance in the module. It must be possible to use a module as an object before it has been completely initialized, though, as the module shown in Figure~\ref{fig:moduleinit} shows.
\begin{figure}
\caption{Module Initialization Example}

\vspace{0.2cm}
\begin{tabular}{c}
\begin{babellisting}
module main
  val y = here.sqr 9 
  val z = y
  def sqr x = x * x 
end
\end{babellisting}
\end{tabular}
\label{fig:moduleinit}
\end{figure}
To initialize module \textsl{main}, we need to evaluate first $y$ and then $z$. Evaluating $y$ involves sending 
the message \textsl{sqr} to \textsl{main}. But at this point, \textsl{main} has not been completely initialized yet!

We solve this problem by keeping track of the progress of the initialization of a module. The progress is measured by the \emph{initialization counter} of the module. When the initialization of the module starts, it is 0. Each time a \babelsrc{val} statement has been evaluated, this counter is increased by 1. For each message of the module we can determine \emph{statically} which initialization counter is required so that all values directly used by this message are available. If during the initialization of the module a message arrives at the module that has a higher initialization counter requirement than the current initialization counter can provide, a dynamic exception is the result. It is not possible to send a message to a module that has not at least started its initialization because:
\begin{enumerate}
\item if the module is \babelsrc{root}, then it always has been  completely initialized; 
\item if the module is \babelsrc{here}, then it obviously has started initialization already;
\item if the module is \babelsrc{m.id}, then the only other means apart from the above of obtaining a reference to it is by sending \babelsrc{id} to \babelsrc{m}; the result of this message send will be a completely initialized module if its initialization has not even started yet or has been completed already; otherwise the result will be a module currently initializing. 
\end{enumerate}

\section{Packages}
\emph{ToDo: need to write this section}

\section{Objects}
Modules already give the developer the ability to define her own objects in Babel-17. This ability is strongly limited, though, because it is possible to determine statically how many module objects there are in a Babel-17 program. A more flexible way of creating objects is provided by the \babelsrc{object} expression which has the following syntax:
\begin{babellisting}
object
  $s_1$
  $\vdots$
  $s_n$
end
\end{babellisting}
The statements $s_i$ are either \babelsrc{val} definitions or optionally attributed \babelsrc{def} statements; the default attribute is \babelsrc{private}. 

A keyword that can be used in object \babelsrc{def} statements is \babelsrc{this}. It denotes the current object. Because the current object exists only after the object has been completely initialized, it must not be used in the \babelsrc{val} statements of the object; neither may it be used by those \babelsrc{def} statements that involve messages which are sent directly or indirectly from the \babelsrc{val} statements of the same object.

Object initialization works similarly to module initialization. But unlike in the module case, no outside reference to the object currently being initialized exists. Because of above restrictions for \babelsrc{this}, we can furthermore determine \emph{statically} if all initialization counters fulfill their requirements. If one doesn't, then this leads to a compile-time error.

The returned object responds to those messages which have corresponding \babelsrc{def} statements. The rules for object access are those for module access. Therefore objects that have been defined in the same module can access all of each others messages, even those which have been declared as \babelsrc{private}. 

There is no inheritance in Babel-17. I think that inheritance is actually \emph{against} the practices of good software engineering, as it often is all about patching objects \emph{after} they have been designed. On the other hand, if objects are extended via inheritance according to a given design, then I think Babel-17 is flexible enough to represent this design without inheritance. 

\section{Boolean Operators}

Babel-17 provides the usual boolean operators. They are just syntactic sugar for certain \babelsrc{match} expressions; the exact translations are given in Table~\ref{tab:booleanops}.
\begin{table}
\caption{Boolean Operators}
\begin{tabular}{c|c|c}
\babelsrc{\! a} & \babelsrc{a \& b} &\babelsrc{a | b} \\\hline
 \small
\begin{babellisting}
match a 
  case true => 
    false 
  case false => 
    true
  case _ => 
    exception TypeError
end
\end{babellisting}
 & 
 \small
\begin{babellisting}
match a 
  case true => 
    match b 
      case true => 
        true
      case false => 
        false
      case _ => 
        exception TypeError
    end 
  case false => 
    false
  case _ => 
    exception TypeError
end
\end{babellisting}
 & 
 \small
\begin{babellisting}
match a 
  case false => 
    match b 
      case true => 
        true
      case false => 
        false
      case _ => 
        exception TypeError
    end 
  case true => 
    true
  case _ => 
    exception TypeError
end
\end{babellisting}
\end{tabular}
\label{tab:booleanops}
\end{table}
Babel-17 also has \babelsrc{if}-expressions with the following syntax:
\begin{babellisting}
if $b_1$ then
  $e_1$
elseif $b_2$ then
  $e_2$
  $\vdots$
elseif $b_n$ then
  $e_n$
else
  $e_{n+1}$
end
\end{babellisting}
The \babelsrc{elseif}-branches are  optional. Also, they can be eliminated in the obvious manner via nesting, so that we only need to give the semantics for the expression
\begin{babellisting}
if $b$ then $e_1$ else $e_2$ end
\end{babellisting}
The meaning of above expression is defined to be
\begin{babellisting}
match $b$ 
  case true => $e_1$
  case false => $e_2$
  case _ => exception TypeError 
end
\end{babellisting}

\section{Order}
Babel-17 has a built-in partial order \babelsrc{$\le$}. All other relational operators are defined in terms of this partial order (Table~\ref{tab:relops}).
\begin{table}
\caption{Relational Operators}
\begin{tabular}{c|c}
\textbf{Syntax} & \textbf{Semantics} \\\hline
$a >= b$ & $b <= a$ \\
$a == b$ & $a <= b\ \&\ b <= a$ \\
$a <> b$ &  $!(a <= b)\ \&\ !(b <= a)$\\
$a < b$ & $a <= b\ \&\ !(a >= b)$ \\
$a > b$ & $a >= b\ \&\ !(a <= b)$ \\
$a$ $!=$ $b$ & $! (a == b)$ \\
\end{tabular}
\label{tab:relops}
\end{table}
It is possible to chain relational operators like this:
\begin{babellisting}
$a$ <= $b$ <= $c$ > $d$ <> $e$ 
\end{babellisting}
The semantics of the above is 
\begin{babellisting}
$a$ <= $b$ & $b$ <= $c$  & $c$ > $d$  & $d$ <> $e$ .
\end{babellisting}
Note that  we always evaluate the operands  of relational operators, even chained ones, only once. For example, the precise semantics of $a <= b <= c <= d <= e$ is not $a <= b\ \&\ b <= c\ \&\  c <= d\ \&\  d <= e$, but rather
\begin{babellisting}
begin
  val t = $a$
  val u = $b$
  t <= u &
  begin
    val v = $c$
    u <= v & 
    begin
      val w = $d$
      v <= w & w <= $e$
    end
  end
end
\end{babellisting}
In the above, \babelsrc{t}, \babelsrc{u}, \babelsrc{v} and \babelsrc{w} are supposed to be fresh identifiers.  Also note that if there are operands that are exceptions, then the result of a comparison is a dynamic exception with the same parameter as the first such operand (from left to right).

The partial order is defined by the following laws:
\begin{itemize}
\item $-\infty < b < z < s < mod < modkey < list < cexpr < f < set < map < \infty$ holds for all
 booleans $b$, integers $z$, strings $s$, module keys $modkey$, modules $mod$, lists $l$, constructed expressions $cexpr$, functions $f$, sets $set$, maps $map$ 
 \item booleans are totally ordered and \babelsrc{false} $<$ \babelsrc{true} holds
 \item integers are totally ordered in the obvious way
 \item $-\infty == -\infty$ and $\infty == \infty$ both hold 
 \item strings are totally ordered via lexicographic ordering
 \item modules are totally ordered by representing them by the lists created from separating the absolute module path by periods
 \item module keys are totally ordered by the ordering on the modules they belong to
\item lists are partially ordered by the lexicographic ordering 
\item constructed expressions are partially ordered by representing them by the pair consisting of constructor and parameter
\item $f <> g$ holds for all functions $f$ and $g$
\item sets are partially ordered by representing them by sorted lists that consist of the elements of the set
\item maps are partially ordered by representing them by sorted lists that consist of the (key, value) pairs of the map
\item let $a$ be a user-defined object (i.e., defined via \babelsrc{object}); if $a$ cannot receive the message \texttt{representative}, then $a <> b$ holds for all $b$; otherwise let $ra$ be the result of sending  \texttt{representative} to $a$ from within the module where $a$ was defined; then $a <= b$ is defined by $ra <= b$, and $b <= a$ is defined via $b <= ra$ for all $b$.
\end{itemize}

The purpose of \emph{module keys} is to provide a secret that can only be obtained by code within the module. Inside a module, the module key can be obtained via
\begin{babellisting}
@
\end{babellisting}
The main application of module keys is to create abstract datatypes that cannot be confused with other types with respect to the built-in partial order of Babel-17. 

\section{Sets and Maps}
Sets and maps are built into Babel-17. For example, the set consisting of 3, 42 and $\infty$ can be written as
\begin{babellisting}
{42, $\infty$, 3}
\end{babellisting}
Sets are always sorted. The default order is Babel-17's built-in partial order, but it is also possible to create sets that work with arbitrary partial orders; an arbitrary partial order is represented as a function that takes a pair and returns a boolean. Adding or removing an element $e$ from a set $S$ is only well-defined when the elements of $S$ together with $e$ are totally ordered by the partial order of $S$. The same holds for testing if an element is in a set. Table~\ref{tab:setops} shows the most commonly used notation for sets. 
\begin{table}
\caption{Set Operations}
\begin{tabular}{c|c}
$S$ \verb!+! $e$ & \tabparbox{set created by inserting the element $e$  into the set $S$} \\\hline
$S$ \verb!-! $e$ & \tabparbox{set created by removing the element $e$  from the set $S$} \\\hline
$S$ \verb!++! $T$ & \tabparbox{set created by inserting all elements of the set/list $T$  into the set $S$} \\\hline
$S$ \verb!--! $T$ & \tabparbox{set created by removing all elements of the set/list $T$ from the set $S$} \\\hline
$S$ \verb!*! $T$ & \tabparbox{cartesian product of the set $S$ and the set $T$, sorted by lexicographic ordering} \\\hline
$S$ \verb!**! $T$ & \tabparbox{set created by removing all elements from the set $S$ which are not in the set $T$} \\\hline
$S$ $e$ & \tabparbox{tests wether $e$ is an element of $S$}\\\hline
$S / f$ & \tabparbox{set created by applying the function $f$ to the elements of $S$}\\\hline
\babelsrc{$S$.reorder $\ p$} & \tabparbox{set created by reordering $S$ according to the partial order $p$; in case of duplicate elements, the greater of the elements relative to the order of $S$ is kept}
\end{tabular}
\label{tab:setops}
\end{table}

Maps map finitely many keys to values. For example, the map that maps 1 to 2 and 4 to 0 is written as
\begin{babellisting}
{1 -> 2, 4 -> 0}
\end{babellisting}
The empty map is denoted by 
\begin{babellisting}
{->}
\end{babellisting}
Maps also have always a partial order associated with them, by default this is Babel-17's built-in partial order.  Operations on maps are only well-defined if all keys of the map together with all other involved keys are totally ordered by the associated order. Table~\ref{tab:mapops} shows the most commonly used notation for maps.
\begin{table}
\caption{Map Operations}
\begin{tabular}{c|c}
$M$ \verb!+! $(k, v)$ & \tabparbox{map created from the map $M$ by associating $k$ with $v$}\\\hline
$M$ \verb!-! $k$ & \tabparbox{map created from the map $M$ by removing the key $k$}\\\hline
$M$ \verb!++! $N$ &  \tabparbox{map created from the map $M$ by adding the key/value pairs of the map/set/list $N$}\\\hline
$M$ \verb!--! $S$ & \tabparbox{map created from $M$ by removing all keys that are in the set/list/map $S$}\\\hline
$M$ \verb!*! $N$ & \tabparbox{map created by using the partial order of $M$; if $(k_M,v_M)$ is contained in $M$ and 
$(k_N, v_N)$ is contained in $N$ such that $k_M == k_N$, then $(k_M, (v_M, v_N))$ is contained in the new map} \\\hline
$M$ \verb!**! $T$ & \tabparbox{map created by removing all keys from the map $M$ which are not in the set/map $T$} \\\hline
$M$ $k$ & \tabparbox{returns the value $v$ associated with $k$ in $M$, or returns a dynamic exception with parameter \texttt{OutOfDomain} if no such value exists} \\\hline
$M \% f$ & \tabparbox{map created by applying the function $f$ to the values of $M$; $f$ takes a key/value pair and returns a value}\\\hline
$M / f$ & \tabparbox{map created by applying the function $f$ to the values of $M$; $f$ takes a value and returns a value}\\\hline
\babelsrc{$M$.reorder $\ p$} & \tabparbox{map created by reordering $M$ according to the partial order $p$; in case of duplicate keys, the greater of the keys relative to the order of $M$ is kept}
\end{tabular}
\label{tab:mapops}
\end{table}

\section{API and Runtime Environment}
Although we have already provided the specification of many operations for the built-in types of Babel-17, this document does not contain the complete API for all types yet. This API will be provided together with a reference implementation for Babel-17 v0.2, which is currently scheduled for the summer of 2010. Until then, let me just make a few comments about it:
\begin{itemize}
\item Integers are arbitrary precision and support the usual operations, throwing exceptions in cases which are not well-defined. 
\item Division and modulo of integers are euclidean. 
\item Strings support the usual operations like concatenation; the basic unit is a code point, not a character. Advanced operations like the Unicode collation algorithm are not part of Babel-17 v0.2, but will maybe introduced in later versions of Babel-17.
\end{itemize}
This specification also does not contain anything about the runtime environment in which Babel-17 is supposed to run. Depending on the runtime environment, there may be additional libraries available to the programmer. 
The medium term goal is to have Babel-17 running on and interfacing with the following platforms:
\begin{itemize}
\item Java
\item Android
\item iPhone / iPad SDK
\item LLVM
\item HTML5 / Javascript 
\end{itemize}

\section{Syntactic Sugar}
One of the goals of Babel-17 is that Babel-17 code is easy to read and understand. I have found that allowing arbitrary user-specific extensions to the syntax of code are definitely not helping to achieve this goal. Nevertheless, a bare minimum of syntactic sugar is necessary to support the most basic conventions known from arithmetic; for example, one should be able to write \texttt{3 + 5} to denote the addition of the integer 3 and the integer 5.

The programmer can use some of this syntactic sugar when defining her own objects. For example, \texttt{3 + 5} is just syntactic sugar for 
\begin{babellisting}
3.syntactic_plus 5
\end{babellisting} 
Table~\ref{tab:syntacticsugar} lists all syntactic sugar of Babel-17 that is also available to the programmer. 
\begin{table}
\caption{Syntactic Sugar}
\begin{tabular}{c|c}
\textbf{Sugared} & \textbf{Desugared} \\\hline\hline
$a$ \verb!+! $b$ & \babelsrc{$a$.syntactic_plus $\ b$} \\\hline
$a$ \verb!-! $b$ & \babelsrc{$a$.syntactic_minus $\ b$} \\\hline
\verb!-! $a$ & \babelsrc{$a$.syntactic_uminus} \\\hline
$a$ \verb!*! $b$ & \babelsrc{$a$.syntactic_times  $\ b$} \\\hline
$a$ \verb!/! $b$ & \babelsrc{$a$.syntactic_div  $\ b$} \\\hline
$a$ \verb!%! $b$ & \babelsrc{$a$.syntactic_mod  $\ b$} \\\hline
$a$ \verb+^+ $b$ & \babelsrc{$a$.syntactic_pow  $\ b$} \\\hline
$a$ \verb!++! $b$ & \babelsrc{$a$.syntactic_plusplus $\ b$} \\\hline
$a$ \verb!--! $b$ & \babelsrc{$a$.syntactic_minusminus $\ b$} \\\hline
$a$ \verb!**! $b$ & \babelsrc{$a$.syntactic_timestimes  $\ b$}\\\hline
$a$ \verb!to! $b$ & \babelsrc{$a$.syntactic_to  $\ b$}\\\hline
$a$ \verb!downto! $b$ & \babelsrc{$a$.syntactic_downto  $\ b$}\\\hline
$f$ $x$ &  \babelsrc{$f$.apply  $\ x$}
\end{tabular}
\label{tab:syntacticsugar}
\end{table}
The availability of syntactic sugar for function application means that you can let your own objects behave as if they were functions. To simplify the implementation of this, there is the restriction that \babelsrc{apply} methods cannot be implemented via a \babelsrc{def} that takes no parameter.

\section{Memoization}
Babel-17 supports \emph{memoization}. 
In those places where \babelsrc{def}-statements can be used, \babelsrc{memoize}-statements can be used, also. A \babelsrc{memoize}-statement must always refer to \babelsrc{def}-statements in the same scope. Babel-17 differentiates two kinds of memoization, \emph{strong} and \emph{weak}. A \babelsrc{memoize}-statement has the following syntax:
\begin{babellisting}
memoize $\metababel{ref}_1 \hdots \metababel{ref}_n$
\end{babellisting}
The $\metababel{ref}_i$ are either of the form $\metababel{id}$ to indicate strong memoization, or of the form $(\metababel{id})$ to signal weak memoization. In both cases $\metababel{id}$ refers to the \babelsrc{def}-statement being memoized. As an example, here is the definition of the weakly memoized fibonacci-sequence:
\begin{babellisting}
memoize (fib)
def fib 0 = 0
def fib 1 = 1
def fib n = fib (n-1) + fib (n-2)
\end{babellisting}
The difference between weak and strong memoization is that strong memoization guarantees that the memoized function will not be executed twice for the same argument; weak memoization does not make this guarantee, so that garbage collection can reclaim all or part of the memoization cache when it needs to. Note that all arguments to the same memoized function must be totally ordered by the built-in partial order.

\section{Linear Scope}
We extend now the syntax of \babelsrc{val}-statements such that it is actually legal to leave out the keyword \babelsrc{val} if all variables defined by it have already been defined  previously in its surrounding \emph{linear scope}. The following two expressions are equivalent:
\begin{center}
\begin{tabular}{ccc}
\begin{babellisting}
begin
  val x = $a$ 
  val y = $b$
  val x = $c$
  $d$
end
\end{babellisting}
& \hspace{2cm} &
\begin{babellisting}
begin
  val x = $a$ 
  val y = $b$
  x = $c$
  $d$
end
\end{babellisting}
\end{tabular}
\end{center}
Furthermore, \babelsrc{begin $\ \hdots\ $ end} can not only be used as an expression, but also as a statement; the following expressions exemplify nested  \babelsrc{begin $\ \hdots\ $ end} statements:
\begin{center}
\begin{tabular}{ccccc}
\begin{babellisting}
begin
  val x = 1 
  val y = 2
  begin
    val x = 3
    val y = 4 * x
  end
  (x, y)
end
\end{babellisting}
& \hspace{1cm} &
\begin{babellisting}
begin
  val x = 1 
  val y = 2
  begin
    val x = 3
    y = 4 * x
  end
  (x, y)
end
\end{babellisting}
& \hspace{1cm} &
\begin{babellisting}
begin
  val x = 1 
  val y = 2
  begin
    val x = 3
    val y = 0
    y = 4 * x
  end
  (x, y)
end
\end{babellisting}\\\hline
evaluates to $(1, 2)$ & &
evaluates to $(1, 12)$ & &
evaluates to $(1, 2)$ \\[0.5cm]
\end{tabular}
\end{center}
The above examples show that the effect of dropping the \babelsrc{val} in a \babelsrc{val} statement is that the binding of an identifier becomes visible at that level within the linear scope where it has last been introduced via a \babelsrc{val} statement that includes the \babelsrc{val} keyword or via a pattern match in a \babelsrc{match} or \babelsrc{def}.

The linear scope of a statement is defined to be the block expression $b$ that directly contains the statement, together with the linear scope of the expression or statement that contains $b$. 
The linear scope of an expression $e$ is only defined when $e$ is a \emph{control expression} that appears in another \babelsrc{val} statement of the form
\begin{babellisting}
val $\metababel{pat}$ = $e$
\end{babellisting}
or
\begin{babellisting}
$\metababel{pat}$ = $e$
\end{babellisting}
Then the linear scope of $e$ is defined as the linear scope of that \babelsrc{val} statement.
These are all \emph{control expressions} of Babel-17:
\begin{itemize}
\item \babelsrc{begin ... end}
\item \babelsrc{if ... end}
\item \babelsrc{match ... end}
\item \babelsrc{for ... end}
\item \babelsrc{while ... end}
\end{itemize}
The last two control expressions are loops and explained in the next section.

Here are three example code snippets that illustrate linear scope:
\begin{center}
\begin{tabular}{ccccc}
\begin{babellisting}
begin
  val x = 1
  val y = 
    begin 
      x = 2 
      x+x 
    end
  (x, y)
end
\end{babellisting}
& \hspace{1cm} &
\begin{babellisting}
begin
  val x = 1
  val y = 3 *
    begin 
      x = 2 
      x+x 
    end
  (x, y)
end
\end{babellisting}
& \hspace{1cm} &
\begin{babellisting}
begin
  val x = 1
  val y = 3 *
    begin 
      val x = 2 
      x+x 
    end
  (x, y)
end
\end{babellisting}\\\hline
evaluates to $(2, 4)$ & &
illegal & &
evaluates to $(1, 12)$ \\[0.5cm]
\end{tabular}
\end{center}

Just as  the \babelsrc{begin ... end} expression may be used as a statement, 
you can also use all other control expressions as statements, for example:
\begin{babellisting}
begin
  val x = random 2
  if x == 0 then
    x = 100
  else
    x = 200
  end
  x + x
end
\end{babellisting}
This expression will evaluate either to $200$ or to $400$.

For \babelsrc{if}-statements the \babelsrc{else}-branch is optional, and \babelsrc{match}-statements do not throw a \babelsrc{NoMatch} exception if none of the patterns matches. 

\section{Yield}
Control expressions always return a value. With the help of the \babelsrc{yield} statement and, optionally, \emph{collector annotations}, the programmer has flexible control about how this value is computed. The syntax of a \babelsrc{yield} statement is simply
\begin{babellisting}
yield $e$
\end{babellisting} 
where $e$ is an arbitrary expression. The semantics is that the value of the control expression is the collection of all the values that have been issued via \babelsrc{yield}. For example, the expression
\begin{babellisting}
begin
  yield 1
  val x = 2
  yield x*x
  yield 3
  10
end
\end{babellisting}
evaluates to \texttt{(1, 4, 3, 10)}. Note how the normal return value of \babelsrc{begin ... end} just counts as an additional \babelsrc{yield}. 

By default, all yielded values are collected in a list which collapses in case of only a single element. The programmer might want to deviate from this default and collect the yielded values differently, for example to get rid of the collapsing behavior. \emph{Collector annotations} allow her to do just that. A collector annotation has the following syntax:
\begin{babellisting}
with $c$ : $e$
\end{babellisting}
where $c$ is a \emph{collector} and $e$ is a control expression. A collector is any object that 
\begin{itemize}
\item responds to the message \verb+collector_close+,
\item and responds to the message \verb+collector_add+ $x$ with another collector.
\end{itemize}
Lists, sets and maps are built-in collectors which the programmer can use out-of-the-box; apart from that she can implement her own collectors, of course.

Here is an example where we use a set as a collector:
\begin{babellisting}
with {4} : begin
  yield 1
  yield 2
  yield 1
  10
end
\end{babellisting}
Above expression evaluates to \babelsrc{\{1, 2, 4, 10\}}.

\section{Loops}
Unlike the other control expressions, \emph{loops} become useful only in combination with \emph{linear scope} and \babelsrc{yield}. 

This is the syntax for the \babelsrc{while}-loop:
\begin{babellisting}
while $c$ do
  $b$
end
\end{babellisting}
Here $c$ must evaluate to a boolean and $b$ is a control block. For example, here is how you could code the euclidean algorithm for calculating the greatest common divisor using \babelsrc{while}:
\begin{babellisting}
def gcd (a,b) = begin
  while b != 0 do
    (a, b) = (b, a mod b)
  end
  a
end
\end{babellisting}

There is also the \babelsrc{for}-loop. It has the following syntax:
\begin{babellisting}
for $p$ in $C$ do
  $b$
end
\end{babellisting}
In the above $p$ is a pattern, $C$ is a \emph{collection} $C$, and $b$ is a control block.
The idea is that above expression iterates through those elements of the \emph{collection} $C$ 
which match $p$; for each successfully matched element, $b$ is executed. 

An object $C$ is a collection if it handles the message \texttt{iterate}
\begin{itemize}
\item by returning \texttt{()} if it represents the empty collection,
\item by returning \texttt{($e$, $C'$)} such that $C'$ is also a collection otherwise.
\end{itemize}

Here is an example of a simple \babelsrc{for}-loop expression:
\begin{babellisting}
begin
  val s = [10, (5, 8), 7, (3,5)]
  with {->} : for (a,b) in s do
    yield (b,a)
  end
end
\end{babellisting}
evaluates to \babelsrc{\{8 -> 5, 5 -> 3\}}.

Using \babelsrc{for}-loops it is possible to formulate all of those \emph{fold}-related functionals known from functional programming in a way which is easier to parse for most people. 
\end{document}  